/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        188.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 15:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个整数数组prices ，它的第 i 个元素prices[i] 是一支给定的股票在第 i 天的价格。
//
//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易

//https://labuladong.gitee.io/algo/动态规划系列/团灭股票问题.html
#include "../header.h"

class Solution {
public:
    int maxProfit(int k, vector<int> &prices) {
        //        dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])
        //        dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
        int n = prices.size();
        if (n == 1) return 0;
        if (k > n / 2) {
            return maxProfit(prices);
        }
        int dp[n][k + 1][2];
        memset(dp,0, sizeof(dp));
        for (int j = k; j >= 1; --j) {
            dp[0][j][0] = 0;
            dp[0][j][1] = -prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = k; j >= 1; --j) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[n-1][k][0];
    }

private:
    int maxProfit(vector<int> &prices) {
        /*
        k == infinity 买入次数
        dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])
                = max(dp[i - 1][k][1], dp[i-1][k][0] - prices[i])
        dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])

         ==> k都存在，可以消去
        dp[i][1] = max(dp[i - 1][1], dp[i-1][0] - prices[i])
        dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
         */
        int n = prices.size();
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (int i = 0; i < n; ++i) {
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }
};